#include <iostream>
#include <string>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };

void display(ListNode *head) {
    ListNode *it = head;
    while (it != NULL) {
        cout << it->val << " ";
        it = it->next;
    }
    cout << endl;
}

ListNode **findSecondList(ListNode *firstList,
 unsigned partition) {
	unsigned i;
    ListNode **secondArray = new ListNode*[2];
	ListNode *secondList = firstList;
    ListNode *bsecond;
    if (firstList == NULL) {
        secondArray[0] = NULL;
        secondArray[1] = NULL;
        return secondArray;
    }
	for (i = 0; i < partition; i++) {
		if(secondList != NULL) {
            bsecond = secondList;
			secondList = secondList->next;
		}
	}
    secondArray[0] = bsecond;
    secondArray[1] = secondList;
	return secondArray;
}

ListNode *sortList(ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    unsigned partition = 1;
    ListNode *bfirst = NULL;
    ListNode *first = head;
    ListNode **secondArray = findSecondList(first, partition);
    ListNode *bsecond = secondArray[0];
    ListNode *second = secondArray[1];
    ListNode **endArray = findSecondList(second, partition);
    ListNode *bend = endArray[0]; 
    ListNode *end = endArray[1];
    while (second != NULL) {
        while (second != NULL) {
            while (second != end && first != second) {
                if  (first->val > second->val) {
                    if (bfirst == NULL) {
                        bsecond->next = second->next;
                        head = second;
                        second->next = first;
                        second = bsecond->next;
                        bfirst = head;
                    } else {
                        bsecond->next = second->next;
                        bfirst->next = second;
                        second->next = first;
                        bfirst = second;
                        second = bsecond->next;
                    }
                } else {
                    if (bfirst == NULL) {
                        bfirst = head;
                    } else {
                        bfirst = bfirst->next;
                    }
                    first = first->next;
                }

            }
            if (second == end) {
                bfirst = bsecond;
            } else {
                bfirst = bend;
            } 
            first = end;
            secondArray = findSecondList(first, partition);
            bsecond = secondArray[0];
            second = secondArray[1];
            endArray = findSecondList(second, partition);
            bend = endArray[0];
            end = endArray[1];
            display(head);            
        }
        partition *= 2;
        bfirst = NULL;
        first = head;
        secondArray = findSecondList(first, partition);
        bsecond = secondArray[0];
        second = secondArray[1];
        endArray = findSecondList(second, partition);
        bend = endArray[0];
        end = endArray[1];
    }
    return head;
}

int main() {
	int i;
	ListNode *head = new ListNode(4);
	ListNode *cur = new ListNode(3);
	head->next = cur;
	for (i = 0; i < 2; i++) {
		ListNode *temp = new ListNode(2-i);
		cur->next = temp;
		cur = temp;
	}

    display(head);
    head = sortList(head);
    display(head);
	return 0;
}